
package org.infoset.xml.memory;

import org.infoset.xml.*;
import org.infoset.xml.util.*;

import java.util.*;
import java.net.*;

public abstract class MemoryParent extends MemoryItem implements Parent {

   class ChildrenByTypeIterator implements Iterator<Child> {
      ItemType type;
      Child next;
      Iterator toCheck;
      ChildrenByTypeIterator(ItemType type) {
         this.type = type;
         this.next = null;
         this.toCheck = children==null ? Collections.EMPTY_LIST.iterator() : children.iterator();
         seek();
      }
      
      void seek() {
         Child found = null;
         if (toCheck.hasNext()) {
            do {
               found = (Child)toCheck.next();
               if (found.getType()!=type) {
                  found = null;
               }
            } while(found==null && toCheck.hasNext());
         }
         next = found;
      }
      
      public boolean hasNext() {
         return next!=null;
      }
      
      public Child next() {
         Child toReturn = next;
         seek();
         return toReturn;
      }
      
      public void remove() {
         throw new UnsupportedOperationException("Removing children via iterator is not allowed.");
      }
      
   }
   
   class RemoveableChildrenIterator implements Iterator {
      int index = 0;
      int last = -1;
      public boolean hasNext() {
         return index<children.size();
      }
      public Object next() {
         if (index>=children.size()) {
            throw new NoSuchElementException("There are no more children to iterate.");
         }
         last = index;
         return children.get(index++);
      }
      
      public void remove() {
         if (last<0) {
            throw new IllegalStateException("The iteration has not been started [next() needs to be called].");
         }  
         synchronized (children) {
            children.remove(last);
            index--;
            int len = children.size();
            for (int i=last; i<len; i++) {
               ((MemoryItem)children.get(i)).setIndex(i);
            }
         }
      }
      
   }
   static class AncestorIterator implements Iterator {
      
      Child item;
      
      AncestorIterator(Child p) {
         item = p;
      }
      public boolean hasNext() {
         return item!=null;
      }
      
      public Object next() {
         Item toReturn = item;
         if (item!=null) {
            item = item.getParent();
         }
         return toReturn;
      }
      
      public void remove() {
         throw new UnsupportedOperationException("remove() not supported on axis iteration.");
      }
      
   }
   
   static class DescendantIterator implements Iterator {

      boolean returnSelf;
      Parent self;
      
      DescendantIterator(Parent self,boolean returnSelf) {
         this.self = self;
         this.returnSelf = returnSelf;
      }
      
      // TODO: implement
      public boolean hasNext() {
         return false;
      }
      
      public Object next() {
         return null;
      }
      
      public void remove() {
         throw new UnsupportedOperationException("remove() not supported on axis iteration.");
      }
      
   }
   
   static class FollowingIterator implements Iterator {
      
      // TODO: implement
      Child current;
      FollowingIterator(Child current) {
         this.current = current;
      }
      
      public boolean hasNext() {
         return false;
      }
      
      public Object next() {
         return null;
      }
      
      public void remove() {
         throw new UnsupportedOperationException("remove() not supported on axis iteration.");
      }
   }
      
   static class PrecedingIterator implements Iterator {
      
      //TODO: implement
      Child current;
      PrecedingIterator(Child current) {
         this.current = current;
      }
      
      public boolean hasNext() {
         return false;
      }
      
      public Object next() {
         return null;
      }
      
      public void remove() {
         throw new UnsupportedOperationException("remove() not supported on axis iteration.");
      }
   }
   
   static class FixRank extends TreeTraversal<Object> {
      double increment;
      double start;
      FixRank(double increment,double start) {
         this.increment = increment;
	 this.start = start;
      }

      public void visit(Child n,boolean isStart) {
         if (isStart) {
            start += increment;
            ((MemoryItem)n).setRank(start);
         }
      }
   }

   protected List<Child> children;
   protected boolean inheritedBaseURI;
   protected URI baseURI;

   protected MemoryParent(Infoset infoset,double ranking,URI base,Parent origin) {
      super(infoset,ranking,origin);
      inheritedBaseURI = false;
      baseURI = base;
      children = null;
   }
   
   public Parent getParent() {
      return origin;
   }

   public URI getBaseURI() {
      if (baseURI==null) {
         return origin==null ? null : origin.getBaseURI();
      } else {
         return (origin!=null && inheritedBaseURI) ? origin.getBaseURI() : baseURI;
      }
   }
   
   public boolean isBaseURIInherited() {
      return inheritedBaseURI || baseURI==null && origin!=null;
   }

   public void setBaseURI(URI base) { 
      baseURI = base;
      inheritedBaseURI = false;
   }
   
   public void setBaseURI(URI base,boolean inherited) { 
      baseURI = base;
      inheritedBaseURI = inherited;
   }
   
   /*
   void cloneChildren(Parent newParent) {
      if (children==null) {
         return;
      }
      if (newParent instanceof Element) {
         Element elementParent = (Element)newParent;
         Iterator creepyChildren = children.iterator();
         while (creepyChildren.hasNext()) {
            Item n = (Item)creepyChildren.next();
            if (n instanceof MemoryElement) {
               Element child = ((MemoryElement)n).cloneMe(elementParent);
               elementParent.appendChild(child);
            } else if (n instanceof Characters) {
               elementParent.appendCharacters(((Characters)n).getText());
            } else {
               throw new RuntimeException("Cannot clone due to unknown child class: "+n.getClass().getName());
            }
         }
      } else {
         throw new UnsupportedOperationException("Cloning document children not implemented.");
      }
   }*/
   
   static private List<Child> emptyList = Collections.emptyList();

   public Iterator<Child> iterator() {
      return children==null ? emptyList.iterator() : new RemoveableChildrenIterator();
   }

   public int size() {
      return children==null ? 0 : children.size();
   }

   public Child get(int index) {
      if (children==null || index<0 || index>=children.size()) {
        return null;
      } else {
         return (Child)children.get(index);
      }
   }

   public boolean remove(Object n) {
      if (children==null) {
         return false;
      }
      boolean removed = children.remove(n);
      if (removed) {
         for (int i=0; i<children.size(); i++) {
            MemoryItem s = (MemoryItem)children.get(i);
            s.setIndex(i);
         }
      }
      return removed;
   }

   public Child remove(int index) {
      if (children==null) {
         return null;
      }
      Child c = children.remove(index);
      for (int i=index; i<children.size(); i++) {
         MemoryItem n = (MemoryItem)children.get(i);
         n.setIndex(i);
      }
      return c;
   }
   
   public List<Child> subList(int start,int len) {
      if (children==null) {
         throw new IndexOutOfBoundsException("List is empty.");
      }
      return children.subList(start,len);
   }
   
   public ListIterator<Child> listIterator(int index) {
      if (children==null) {
         throw new IndexOutOfBoundsException("List is empty");
      }
      return children.listIterator(index);
   }
   
   public ListIterator<Child> listIterator() {
      return children==null ? emptyList.listIterator() : children.listIterator();
   }
   
   public int lastIndexOf(Object o) {
      return children==null ? -1 : children.lastIndexOf(o);
   }

   public int indexOf(Object o) {
      return children==null ? -1 : children.indexOf(o);
   }

   void fixChildrenRank(Parent cp) {
      if (cp.size()>0) {
         double increment;
         // no right subtree
         if (getFollowingSibling()==null && cp.getFollowingSibling()==null) {
            // simple case, no bound
            increment = 1;
         } else {
            // calculate increment via number of descendants
            // Count the descendant nodes:
            TreeTraversal<Integer> count = new TreeTraversal<Integer>() {
               int theCount;
	       public void start(Integer context) {
                  theCount = 0;
	       }
	       public Integer end() {
                  return new Integer(theCount);
	       }
	       public void visit(Child item,boolean isStart) {
                  if (isStart) {
                     theCount++;
                  }
	       }
	    };
	    Integer childCount = count.traverse(cp);
            increment = (((MemoryItem)getFollowingSibling()).getRank()-((MemoryItem)cp).getRank())/childCount.intValue();
	 }
         // set all the ranks for the descendants
         FixRank fixIt = new FixRank(increment,((MemoryItem)cp).getRank());
         fixIt.traverseChildren(cp);
      }
   }

   double getHighestRank() {
      // If no children, use this elements rank
      if (children==null || children.size()==0) {
         return ranking;
      } else {
         // Get the right most child
         Item child = (Item)children.get(children.size()-1);
         if (child instanceof Parent) {
            return ((MemoryParent)child).getHighestRank();
         } else {
            return ((MemoryItem)child).getRank();
         }
      }
   }

   public boolean add(Child n) {

      ((MemoryItem)n).setOrigin(this);
      
      if (children==null) {
         children = new ArrayList();
      }

      // calculate child ranking

      double childRank;

      // Simple case: Is the right subtree empty?
      if (getFollowingSibling()==null) {
         // If first child, use self
         if (children.size()==0) {
            childRank = ranking+1;
         } else {
            // find highest rank in subtree
            Item prevChild = (Item)children.get(children.size()-1);
            if (prevChild instanceof Parent) {
               childRank = ((MemoryParent)prevChild).getHighestRank()+1;
            } else {
               childRank = ((MemoryItem)prevChild).getRank()+1;
            }
         }
      } else {
         // Complex case: following sibling
         if (children.size()==0) {
            // Rank is halfway between following sibling's rank and the this node
            childRank = getRank()+((((MemoryItem)getFollowingSibling()).getRank()-getRank())/2);
         } else {
            Item lastChild = (Item)children.get(children.size()-1);
            // Rank is halfway between following sibling's rank and the last
            // child's rank.
            childRank = ((MemoryItem)lastChild).getRank()+((((MemoryItem)getFollowingSibling()).getRank()-((MemoryItem)lastChild).getRank())/2);
         }
      }

      ((MemoryItem)n).setRank(childRank);

      // add the child
      boolean retval = children.add(n);
      ((MemoryItem)n).setIndex(children.size()-1);
      //System.err.println("Appended "+n+" at "+XPathUtils.toXPath(n));

      // Does child have children (and need ranking fixed)?
      if (n instanceof Parent) {
         Parent cp = (Parent)n;
         fixChildrenRank(cp);
      }
      //System.err.println("Appended "+n+" at "+XPathUtils.toXPath(n));

      return retval;
   }

   public Child set(int index,Child n) { 
      if (children==null) {
         throw new IndexOutOfBoundsException("Index "+index+" out of bounds for children.");
      }
      Child current = children.get(index);
      ((MemoryItem)n).setRank(((MemoryItem)current).getRank());
      children.set(index, n);
      return current;
   }
   
   public void clear() {
      children = null;
   }
   
   public boolean retainAll(Collection<?> c) {
      throw new UnsupportedOperationException("Not supported.");
   }
   
   public boolean removeAll(Collection<?> c) {
      if (children==null) {
         return false;
      }
      boolean removed = children.removeAll(c);
      if (removed) {
         for (int i=0; i<children.size(); i++) {
            MemoryItem s = (MemoryItem)children.get(i);
            s.setIndex(i);
         }
      }
      return removed;
   }
   
   public boolean addAll(Collection<? extends Child> collection) {
      for (Child c : collection) {
         add(c);
      }
      return true;
   }
   
   public boolean addAll(int index,Collection<? extends Child> collection) {
      for (Child c : collection) {
         add(index++,c);
      }
      return true;
   }
   
   public boolean containsAll(Collection<?> collection) {
      if (children==null) {
         return collection.size()==0;
      }
      for (Object c : collection) {
         if (!children.contains(c)) {
            return false;
         }
      }
      return true;
   }
   
   public void add(int index,Child n) { 

      if (children==null) {
         children = new ArrayList();
      }

      // calculate child ranking

      double childRank;

      if (index<children.size()) {
         Child before = (Child)children.get(index);

         // Simple case: there is no previous sibling
         if (before.getPrecedingSibling()==null) {
            // rank is half way between parent and node
            childRank = ranking+((((MemoryItem)before).getRank()-ranking)/2);
         } else {
            // Complex case: previous sibling
            Item prev = before.getPrecedingSibling();
            if (prev instanceof Parent) {
               Parent pp = (Parent)prev;
               Item lastChild = (Item)pp.get(pp.size()-1);
               // Rank is halfway between previous sibling's last child's rank and
               // the node's rank.
               childRank = ((MemoryItem)lastChild).getRank()+((((MemoryItem)before).getRank()-((MemoryItem)lastChild).getRank())/2);
            } else {
               // Rank is halfway between previous sibling's rank and node's rank.
               childRank = ((MemoryItem)prev).getRank()+((((MemoryItem)before).getRank()-((MemoryItem)prev).getRank())/2);
            }
         }
      } else if (children.size()==0) {
         childRank = ranking+1;
      } else {
         throw new IllegalArgumentException("The child position "+index+" is greater than the number of children ("+children.size()+")");
      }

      ((MemoryItem)n).setRank(childRank);

      // fix sibling indexes
      for (int i=index; i<children.size(); i++) {
         MemoryItem s = (MemoryItem)children.get(i);
         s.setIndex(i+1);
      }

      // add child in position
      children.add(index,n);

      // set sibling index
      ((MemoryItem)n).setIndex(index);

      // Does child have children (and need ranking fixed)?
      if (n instanceof Parent) {
         Parent cp = (Parent)n;
         fixChildrenRank(cp);
      }
      
   }
   
   public boolean contains(Object o) {
      return children==null ? false : children.contains(o);
   }
   
   public boolean isEmpty() {
      return children==null || children.isEmpty();
   }
   
   public void swapChild(Child oldChild,Child newChild) {
      if (children==null) {
         return;
      }

      int index = children.indexOf(oldChild);
      if (index<0) {
         RuntimeException ex = new RuntimeException("Child being swapped not contained in parent: "+oldChild);
         //ex.printStackTrace();
         throw ex;
         
      }
      children.remove(index);
      children.add(index,newChild);
      if (children.indexOf(newChild)!=index) {
         RuntimeException ex = new RuntimeException("Internal error: child not swapped properly "+newChild);
         //ex.printStackTrace();
         throw ex;
      }
      ((MemoryItem)newChild).setIndex(index);
   }
   
   //public abstract Object clone();
   
   public Iterator getAxis(Infoset.Axis axis) {
      switch(axis) {
         case AncestorAxis:
            return new AncestorIterator(getParent());
         case AncestorOrSelfAxis:
            return new AncestorIterator(this);
         case PrecedingAxis:
            return new PrecedingIterator(this);
         case FollowingAxis:
            return new FollowingIterator(this);
         case PrecedingSiblingAxis:
            return new MemoryItem.PreviousSiblings(getPrecedingSibling());
         case FollowingSiblingAxis:
            return new MemoryItem.FollowingSiblings(getFollowingSibling());
         case ChildAxis:
            return children.iterator();
         case DescendantAxis:
            return new DescendantIterator(this,false);
         case DescendantOrSelfAxis:
            return new DescendantIterator(this,true);
         case SelfAxis:
            return Collections.singletonList(this).iterator();
         case ParentAxis:
            return Collections.singletonList(getParent()).iterator();
         default:
            return super.getAxis(axis);
      }
   }

   public Iterator<Child> getChildrenByType(ItemType type) {
      return new ChildrenByTypeIterator(type);
   }   
   
   public <Child> Child [] toArray(Child [] array) {
      if (children==null) {
         return array;
      }
      return children.toArray(array);
   }
   
   public Object[] toArray() {
      if (children==null) {
         return new Object[0];
      }
      return children.toArray();
   }
   
}
